__author__ = 'st316'
'''
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?
'''


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        return self.val


class Solution:
    # @param head, a ListNode
    # @return a boolean
    def hasCycle(self, head):
        if not head:
            return False
        p = head
        q = head
        while p.next and q.next and q.next.next:
            p = p.next
            q = q.next.next
            if p == q:
                return True
        return False


if __name__ == '__main__':
    s = Solution()
    head = ListNode(1)
    head.next = ListNode(1)
    print s.hasCycle(head)